vivian blog

Repeated Substring Pattern

发表于

需求

需求链接

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

解决思路

问题给了我们一个字符串，问能否拆成n个重复的子串。因此既然能拆分，那么每个子串的长度不能大于原字串长度的一半，那么我们可以从源字符串长度的一半遍历到1，如果当前长度能被总长度整除，说明可以分成若干个字符串，我们将这些子字符串拼接起来看跟原字符串是否相等。 如果拆完了都不相等，返回false。

解决方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var repeatedSubstringPattern = function(s) {
    var len = s.length;
    if(s.length===1){
        return false;
    }
    for(var i = Math.ceil(len/2);i>=1;i--) {//至少得两个元素，才能看看是不是重复
        if(len%i===0) {
            //如果能被整除，说明能分成若干个字符串，然后将这若干字符串拼接起来后的字符串，跟源字符串相等的话，那就说明相等，否则不等
            var c = len/i,t='';
            for(var j = 0;j<c;j++){
                t+=s.substr(0,i);
            }
            if(t===s) {
                return true;
            }
        }
    }
    return false;
};